package com.dataStructure.图;

import com.dataStructure.图.heap.MinHeap;
import com.dataStructure.并查集.通用的并查集_带泛型;

import java.util.*;
import java.util.List;

@SuppressWarnings("ALL")
public class 图_基于邻接表实现<V, E> extends 图<V, E> {
    /**
     * 构造方法
     */
    public 图_基于邻接表实现() {
    }

    public 图_基于邻接表实现(WeightManager<E> weightManager) {
        super(weightManager);
    }

    /**
     * 边权值的比较器
     */
    private Comparator<Edge<V, E>> edgeComparator = (Edge<V, E> e1, Edge<V, E> e2) -> {
        return weightManager.compare(e1.weight, e2.weight);
    };

    /**
     *  这个map存储图所有的顶点，map的键为顶点中的值（对外暴露的不是顶点对象，而是顶点对象中存储的值V），map的值为V对应的的对象
     */
    private Map<V, Vertex<V, E>> vertices = new HashMap<>();

    /**
     * 顶点
     * @param <V>
     * @param <E>
     */
    private static class Vertex<V, E> {
        V value;
        Set<Edge<V, E>> inEdges = new HashSet<>();
        Set<Edge<V, E>> outEdges = new HashSet<>();

        Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            return Objects.equals(value, ((Vertex<V, E>) obj).value);
        }

        @Override
        public int hashCode() {
            return value == null ? 0 : value.hashCode();
        }

        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }

    /**
     * 这个set放着这个图的所有的边
     */
    private Set<Edge<V, E>> edges = new HashSet<>();

    /**
     * 边
     * @param <V>
     * @param <E>
     */
    private static class Edge<V, E> {
        Vertex<V, E> from;
        Vertex<V, E> to;
        E weight;

        Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }

        /**
         * Edge to EdgeInfo method
         * @return
         */
        EdgeInfo<V, E> info() {
            return new EdgeInfo<V, E>(from.value, to.value, weight);
        }

        /**
         * equals方法规则：起点跟终点相等就是同一条边
         * @param o
         * @return
         */
        @Override
        public boolean equals(Object o) {
            Edge<V, E> edge = (Edge<V, E>) o;
            return Objects.equals(from, edge.from) &&
                    Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            int fromCode = from.hashCode();
            int toCode = to.hashCode();
            return fromCode * 31 + toCode;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }

    /**
     * 添加顶点
     * @param v
     */
    @Override
    public void addVertex(V v) {
        if (vertices.containsKey(v)) return;
        vertices.put(v, new Vertex<>(v));
    }

    /**
     * 添加边
     * @param from
     * @param to
     */
    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    /**
     * 添加边带权值
     * @param fromValue
     * @param toValue
     * @param weight
     */
    @Override
    public void addEdge(V fromValue, V toValue, E weight) {
        //判断from，to顶点是否存在
        Vertex<V, E> fromVertext = vertices.get(fromValue);
        //如果fromVertext不存在
        if (fromVertext == null) {
            //不存在则直接新new一个顶点，并且将它放到属于顶点的Map里面去
            fromVertext = new Vertex<>(fromValue);
            vertices.put(fromValue, fromVertext);
        }

        Vertex<V, E> toVertext = vertices.get(toValue);
        //如果toVertext不存在
        if (toVertext == null) {
            //不存在则直接新new一个顶点，并且将它放到属于顶点的Map里面去
            toVertext = new Vertex<>(toValue);
            vertices.put(toValue, toVertext);
        }

        //（判断这两个顶点之间存不存在边），并且new一个新的边
        Edge<V, E> edge = new Edge<>(fromVertext, toVertext);
        //将权重赋值给new的这个edge
        edge.weight = weight;

        //删除后再添加
        //为什么不先判断有没有再决定添加不添加，而是要统一删除后添加？
        //1. 如果判断有没有这个edge，要遍历Set,才能知道有没有这个key，时间复杂度是O(n)
        //2. 如果要判断，代码量变多，直接删除后再添加，无论有没有只用这一套代码都可以
        if (fromVertext.outEdges.remove(edge)) {
            //remove方法返回值是是否删除成功，如果成功删除了outEdeg，才能删除inEdges
            //另外重写了Edge的equals和hashCode方法，remove的时候不会引起歧义
            toVertext.inEdges.remove(edge);
            edges.remove(edge);
        }
        fromVertext.outEdges.add(edge);
        toVertext.inEdges.add(edge);
        edges.add(edge);
    }

    /**
     * 移除顶点
     * @param v
     */
    @Override
    public void removeVertext(V v) {
        //直接删除要传入的顶点，remove方法会返回对应的 value，即为这个顶点对应的vertex
        Vertex<V, E> vertex = vertices.remove(v);

        //如果并不存在这个v对应的顶点，那么返回值为 null，直接return
        if (vertex == null) return;

        //来到这里，那么要开始删除这个顶底有关的边

        //遍历这个vertex的outEdges，inEdges，将它们从set中移除
        //不能一边遍历，一边删东西。如果非要这么做，那么使用迭代器
//        vertex.outEdges.forEach((Edge<V,E> edge)->{
//            removeEdge(edge.from.value,edge.to.value);
//        });
//        vertex.inEdges.forEach((Edge<V,E> edge)->{
//            removeEdge(edge.from.value,edge.to.value);
//        });

        //遍历这个vertex的outEdges，inEdges，使用迭代器将它们从set中移除
        //删除vertex的outEdges，inEdges的同时，也要删除对应顶点的inEdges，outEdges
        // （vertex的outEdeg必然对应其他顶点的inEdeg，vertex的inEdeg必然对应其他顶点的outEdeg，需要一起删掉）
        for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext(); ) {
            Edge<V, E> edge = iterator.next();

            //删除对应顶点的inEdges
            edge.to.inEdges.remove(edge);

            //删除vertex的这一个outEdges
            //把当前遍历到的元素删除，用迭代器保证这种做法是安全的
            iterator.remove();

            //保存图的所有边edegs，这个大集合也要将这条边删掉
            edges.remove(edge);
        }
        for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext(); ) {
            Edge<V, E> edge = iterator.next();

            //删除对应顶点的outEdges
            edge.from.outEdges.remove(edge);

            //删除vertex的这一个inEdges
            //把当前遍历到的元素删除，用迭代器保证这种做法是安全的
            iterator.remove();

            //保存图的所有边edegs，这个大集合也要将这条边删掉
            edges.remove(edge);

        }
    }

    /**
     * 移除边
     * @param from
     * @param to
     */
    @Override
    public void removeEdge(V from, V to) {
        //先判断两个顶点存在不存在
        Vertex<V, E> fromVertext = vertices.get(from);
        if (fromVertext == null) return;
        Vertex<V, E> toVertext = vertices.get(to);
        if (toVertext == null) return;

        //判断from -> to的这条边存不存在
        Edge<V, E> edge = new Edge<>(fromVertext, toVertext);
        //如果存在就删掉
        if (fromVertext.outEdges.remove(edge)) {
            //fromVertext存在outEdge，那么toVertext必定存在inEdge，那么一起删掉
            //remove方法返回值是是否删除成功，如果成功删除了outEdeg，才能删除inEdges
            //另外重写了Edge的equals和hashCode方法，remove的时候不会引起歧义
            toVertext.inEdges.remove(edge);
            edges.remove(edge);
        }
    }

    /**
     * 返回边的数量
     * @return
     */
    @Override
    public int edgesSize() {
        return edges.size();
    }

    /**
     * 返回顶点的数量
     * @return
     */
    @Override
    public int verticseSize() {
        return vertices.size();
    }

    /**
     * 调用这个方法可以打印这个图
     */
    public void print() {
        System.out.println("[顶点]-----------------------------");
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            System.out.println(v);
            System.out.println("out..................");
            System.out.println(vertex.outEdges);
            System.out.println("in..................");
            System.out.println(vertex.inEdges);
        });

        System.out.println("[边]-----------------------------");
        edges.forEach((Edge<V, E> edge) -> {
            System.out.println(edge);
        });
    }

    /***************************************************
     以下遍历图的做法均为打印节点值到控制台，未使用遍历接口 VertexVisitor
     ***************************************************/

    /*   //广度优先遍历 非递归
    @Override
    public void bfs_non_recursive(V begin) {
        //从begin的地方开始遍历图
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null )return;

        //使用一个set来存储遍历过的节点，防止重复入队
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();

        //参照二叉树的层序遍历，使用一个队列来遍历图
        Queue<Vertex<V, E>> queue = new LinkedList<>();

        //开始遍历的顶点入队，相当于二叉树的根节点入队
        queue.offer(beginVertex);

        //将这个遍历过的节点放入visitedVertices中 表示已经遍历过
        visitedVertices.add(beginVertex);

        while (!queue.isEmpty()) {
            //队头顶点出队
            Vertex<V, E> vertex = queue.poll();
            //遍历方式为输出
            System.out.println(vertex.value);

            //将这个遍历过的节点放入visitedVertices中 表示已经遍历过
            visitedVertices.add(vertex);

            //循环遍历vertex的outEdegs，目的是将距离 vertex 单位为一的顶点入队，
            // 即 vertex.Set<outEdges>.to放入队列
            for (Edge<V, E> edge : vertex.outEdges) {

                //如果这个节点已经遍历过了，continue
                if (visitedVertices.contains(edge.to)) continue;

                //放入队列
                queue.offer(edge.to);

                //这个顶点在放入队列后，就应该立即放在visitedVertices中
                //将这个遍历过的节点放入visitedVertices中 表示已经遍历过
                visitedVertices.add(edge.to);
            }
        }
    }

    //深度优先搜索，递归版本
    @Override
    public void dfs_recursion(V begin) {
        //从begin的地方开始遍历图
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null )return;

        //使用一个set来存储遍历过的节点，防止重复遍历
        Set<Vertex<V, E>> visitedVertices ;

        //递归完成深度优先搜索
        dfs_recursion(beginVertex, new HashSet<>());

    }
    private void dfs_recursion(Vertex<V, E> vertex ,Set<Vertex<V, E>> visitedVertices ) {
        //输出遍历自己
        System.out.println(vertex.value);

        //将这个遍历过的节点放入visitedVertices中 表示已经遍历过
        visitedVertices.add(vertex);

        //将自己指向的下一个节点传入dfs中，完成递归遍历的目的
        for (Edge<V, E> edge : vertex.outEdges) {
            //如果这个节点已经遍历过了，continue
            if (visitedVertices.contains(edge.to)) continue;
            //递归
            dfs_recursion(edge.to,visitedVertices);
        }
    }

    //深度优先搜索，非递归版本 （使用栈实现）
    @Override
    public void dfs_non_recursive(V begin) {
        //从begin的地方开始遍历图
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null )return;

        //使用一个set来存储遍历过的节点，防止重复遍历
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        //使用一个栈，来实现遍历
        Stack<Vertex<V,E>> stack = new Stack<>();

        //先访问起点
        stack.push(beginVertex);
        //放入 已访问set，防止重复访问
        visitedVertices.add(beginVertex);
        System.out.println(beginVertex.value);

        while (!stack.isEmpty()) {
            //栈顶元素出栈
            Vertex<V, E> vertex = stack.pop();

            //循环遍历此vertex的outEdges
            for (Edge<V, E> edge : vertex.outEdges) {
                //如果这条边的to在visitedVertices中说明被遍历过 直接continue
                if (visitedVertices.contains(edge.to)) continue;

                ///否则将这条边的from，to进栈
                stack.push(edge.from);
                stack.push(edge.to);
                //将to这个节点放入visitedVertices并遍历
                visitedVertices.add(edge.to);
                System.out.println(edge.to.value);

                //直接break掉
                break;
            }
        }
    }*/

    /*************************************
    以下遍历图的做法使用遍历接口 VertexVisitor
    **************************************/

    /**
     * 广度优先遍历
     * @param begin
     * @param visitor
     */
    @Override
    public void bfs_non_recursive(V begin, VertexVisitor<V> visitor) {
        //如果访问器为空直接返回
        if (visitor == null) return;

        //从begin的地方开始遍历图
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        //使用一个set来存储遍历过的节点，防止重复入队
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();

        //参照二叉树的层序遍历，使用一个队列来遍历图
        Queue<Vertex<V, E>> queue = new LinkedList<>();

        //开始遍历的顶点入队，相当于二叉树的根节点入队
        queue.offer(beginVertex);

        //将这个遍历过的节点放入visitedVertices中 表示已经遍历过
        visitedVertices.add(beginVertex);

        while (!queue.isEmpty()) {
            //队头顶点出队
            Vertex<V, E> vertex = queue.poll();

            //遍历使用VertexVisitor接口
            //如果visit方法返回为true说明终止遍历，直接return
            if (visitor.visit(vertex.value)) return;

            //将这个遍历过的节点放入visitedVertices中 表示已经遍历过
            visitedVertices.add(vertex);

            //循环遍历vertex的outEdegs，目的是将距离 vertex 单位为一的顶点入队，
            // 即 vertex.Set<outEdges>.to放入队列
            for (Edge<V, E> edge : vertex.outEdges) {

                //如果这个节点已经遍历过了，continue
                if (visitedVertices.contains(edge.to)) continue;

                //放入队列
                queue.offer(edge.to);

                //这个顶点在放入队列后，就应该立即放在visitedVertices中
                //将这个遍历过的节点放入visitedVertices中 表示已经遍历过
                visitedVertices.add(edge.to);
            }
        }
    }

    /**
     * 深度优先遍历
     * @param begin
     * @param visitor
     */
    @Override
    public void dfs_non_recursive(V begin, VertexVisitor<V> visitor) {
        //如果访问器为空直接返回
        if (visitor == null) return;

        //从begin的地方开始遍历图
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        //使用一个set来存储遍历过的节点，防止重复遍历
        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        //使用一个栈，来实现遍历
        Stack<Vertex<V, E>> stack = new Stack<>();

        //先访问起点
        stack.push(beginVertex);

        //放入 已访问set，防止重复访问
        visitedVertices.add(beginVertex);

        //遍历使用VertexVisitor接口
        //如果visit方法返回为true说明终止遍历，直接return
        if (visitor.visit(begin)) return;

        while (!stack.isEmpty()) {
            //栈顶元素出栈
            Vertex<V, E> vertex = stack.pop();

            //循环遍历此vertex的outEdges
            for (Edge<V, E> edge : vertex.outEdges) {
                //如果这条边的to在visitedVertices中说明被遍历过 直接continue
                if (visitedVertices.contains(edge.to)) continue;

                ///否则将这条边的from，to进栈
                stack.push(edge.from);
                stack.push(edge.to);
                //将to这个节点放入visitedVertices并遍历
                visitedVertices.add(edge.to);

                //遍历使用VertexVisitor接口
                //如果visit方法返回为true说明终止遍历，直接return
                if (visitor.visit(edge.to.value)) return;

                //直接break掉
                break;
            }
        }
    }

    @Override
    public void dfs_recursion(V begin, VertexVisitor<V> visitor) {

    }

    /**
     * 拓扑排序
     * @return
     */
    @Override
    public List<V> topologicalSort() {
        //创建一个list来存放结果
        List<V> list = new ArrayList<>();

        //创建一个队列，用于保存 0 个入度边的节点
        Queue<Vertex<V, E>> queue = new LinkedList<>();

        //创建一个map来存放每个顶点及其对应的入度边
        Map<Vertex<V, E>, Integer> ins = new HashMap<>();

        //1.初始化：将度为零的节点放入队列；同时维护一个映射map，每个顶点及其对应的入度边存放在map里面
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            //取得入度边in
            int in = vertex.inEdges.size();

            //将度为零的节点放入队列
            if (in == 0) {
                queue.offer(vertex);
            } else {
                //每个顶点及其对应的入度边存放在map里面
                ins.put(vertex, in);
            }
        });

        //2.如果队列不为空
        while (!queue.isEmpty()) {
            //在队列中取出节点
            Vertex<V, E> vertex = queue.poll();

            //放入到返回结果list中
            list.add(vertex.value);

            //遍历节点的outEdges，
            for (Edge<V, E> edge : vertex.outEdges) {
                //将以此 outEdge作为 toEdge的节点的toEdge数量减一
                int toIn = ins.get(edge.to) - 1;
                //如果此时edge.to的入度边已经减为0，将此edge.to放入队列中
                if (toIn == 0) {
                    queue.offer(edge.to);
                } else {
                    //反之重新放入map中，相当于是更新此节点数量
                    ins.put(edge.to, toIn);
                }
            }
        }
        return list;
    }

    /**
     * 最小生成树
     * @return
     */
    @Override
    public Set<EdgeInfo<V, E>> mst() {
        return Math.random() > 0.5 ? prim() : kruskal();
    }
    //使用prim算法实现最小生成树
    public Set<EdgeInfo<V, E>> prim() {
        //如果是一个空图则直接返回
        Iterator<Vertex<V, E>> it = vertices.values().iterator();
        if (!it.hasNext()) return null;

        //将来这个set装最小生成树的边且作为方法返回值
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        //这个set装edgeInfos中边的顶点，解决重复出边的问题
        Set<Vertex<V, E>> addedVertices = new HashSet<>();

        //随机拿出一个顶点作为起始的顶点
        Vertex<V, E> vertex = it.next();

        //这个顶点装到addedVertices中
        addedVertices.add(vertex);

        //因为要找顶点横切边里面的最小的边
        //在这里new一个小顶堆,
        //构造方法中传入可以比较的对象（指定的可比较的泛型对象实现了Comparable接口）以此来构建小顶堆
        //也可以传入一个比较器Comparator
        /*PriorityQueue<Edge<V,E>> heap = new PriorityQueue<>((Edge<V,E> e1,Edge<V,E> e2)->{
            return 0;
        });
        //在堆中加入比较器后，挨个加入元素形成小顶堆
        for (Edge<V, E> edge : vertex.outEdges) {
            heap.offer(edge);
        }*/

        //使用自定义的堆：传入集合和比较器来建一个小顶堆
        MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);


        //当堆不为空;
        //当edgeInfos的size为vertices.size() - 1时，循环也可以结束
        // 最小生成树已经产生，这时候堆没有必要再remove了（即使这时候heap不为空）
        int edgeSize = vertices.size() - 1;
        //int verticesSize = vertices.size();
        //while (!heap.isEmpty() && addedVertices.size() < verticesSize) {...}
        while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
            //拿到权值最小的一条边
            Edge<V, E> edge = heap.remove();
            //解决重复加入的边的问题，一旦发现这条权值最小的边已经出去过就cotinue
            if (addedVertices.contains(edge.to)) continue;

            //prim算法开始：
            //------------------------
            //将这条边加入edgeInfos中
            edgeInfos.add(edge.info());
            //将edge.to节点加入到addedVertices
            addedVertices.add(edge.to);
            //再将这条边的to节点的outEdges加入到heap中
            //这样做会重复加入边
            heap.addAll(edge.to.outEdges);
            //------------------------------
        }


        return edgeInfos;
    }
    /**
     * 使用kruskal算法实现最小生成树
     * @return
     */
    public Set<EdgeInfo<V, E>> kruskal() {
        //没有任何一个点就返回
        int edgeSize = vertices.size() - 1;
        if (edgeSize == -1) return null;

        //将来这个set装最小生成树的边且作为方法返回值
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();

        //使用一个最小堆
        MinHeap<Edge<V, E>> heap = new MinHeap<>(edges, edgeComparator);

        //使用这个并查集来判断是否成环
        通用的并查集_带泛型<Vertex<V, E>> uf = new 通用的并查集_带泛型<>();
        vertices.forEach((V v, Vertex<V, E> vertiex) -> {
            uf.makeSet(vertiex);
        });


        while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
            //拿到权值最小的一条边
            Edge<V, E> edge = heap.remove();

            //如果这条边加进去，构成环
            //使用并查集判断是否形成环
            //当edge的from和to在一个并查集，则必然构成环
            if (uf.isSame(edge.from, edge.to)) continue;

            //不构成环，将这条边加入edgeInfos中
            edgeInfos.add(edge.info());

            //加入并查集
            uf.union(edge.from, edge.to);
        }
        return edgeInfos;
    }

    /**
     * 最短路径算法，实现有Dijkstra算法，Bellman-ford算法
     *
     * @param begin
     * @return
     */
    public  Map<V,PathInfo<V,E>> shortestPath(V begin){
        return this.Dijkstra2(begin);
    }
    /**
     * 最短路径 Dijkstra算法
     * Dijkstra第一种写法,这里的Dijkstra返回的信息比较少（路径信息仅有E来表示总权值）
     * 找定义的起点到其他各个点的最短路径，这里的V为某个顶点，E为起点要到这个点的总权值
     *
     * @param begin
     * @return
     */
    public Map<V, E> Dijkstra1(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;

        //存放用来更新的，不断通过松弛操作来更新值，
        //更新完之后就将最小的值放到selectPaths里面去代表它被拽起来了
        //再将它从 paths中 remove
        Map<Vertex<V, E>, E> paths = new HashMap<>();
        Map<V, E> selectPaths = new HashMap<>();
        //初始化paths
        for (Edge<V, E> edge : beginVertex.outEdges) {
            paths.put(edge.to, edge.weight);
        }

        while (!paths.isEmpty()) {
            Map.Entry<Vertex<V, E>, E> minEntry = getMinPath1(paths);
            //minEntry离开桌面
            Vertex<V, E> minVertex = minEntry.getKey();
            selectPaths.put(minVertex.value, minEntry.getValue());
            paths.remove(minVertex);
            //对 minVertex 的 outEdegs 进行松弛操作
            for (Edge<V, E> edge : minVertex.outEdges) {
                //如果edge.to已经离开桌面，或者edge.to是起点，就没有必要进行松弛操作
                if (selectPaths.containsKey(edge.to.value)) continue;
                //新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
                E newWeight = weightManager.add(minEntry.getValue(), edge.weight);
                //以前的最短路径：beginVertex到edge.to的最短路径
                E oldWeight = paths.get(edge.to);
                if (oldWeight == null || weightManager.compare(newWeight, oldWeight) < 0) {
                    paths.put(edge.to, newWeight);
                }
            }
        }
        selectPaths.remove(begin);
        return selectPaths;
    }
    /**
     * 第一种 Dijkstra 的 getMinPath 方法，从path里面挑一个最小的路径出来
     *
     * @param paths
     * @return
     */
    private Map.Entry<Vertex<V, E>, E> getMinPath1(Map<Vertex<V, E>, E> paths) {
        Iterator<Map.Entry<Vertex<V, E>, E>> it = paths.entrySet().iterator();
        Map.Entry<Vertex<V, E>, E> minEntry = it.next();
        while (it.hasNext()) {
            Map.Entry<Vertex<V, E>, E> entry = it.next();
            if (weightManager.compare(entry.getValue(), minEntry.getValue()) < 0) {
                minEntry = entry;
            }
        }
        return minEntry;
        //Vertex<V, E> minVertex = null;
        //E minWeight = null;
        //
        ////遍历 paths 找到里面最小的权值：minWeight ，拥有最小权值的顶点：Vertex
        //for (Map.Entry<Vertex<V, E>, E> entry : paths.entrySet()) {
        //    E weight = entry.getValue();
        //    if (minVertex == null || weightManager.compare(weight,minWeight) < 0) {
        //        minVertex = entry.getKey();
        //        minWeight = weight;
        //    }
        //}
        //return minVertex;
    }

    /**
     * 最短路径Dijkstra的第二种写法,这里的Dijkstra返回的信息用pageInfo来表示
     * 上面的E为起点要到这个点的总权值，E要表示的信息太少了，在这个地方加一个PathInfo类来表示路径信息
     *
     * @param begin
     * @return
     */
    public Map<V, PathInfo<V, E>> Dijkstra2(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;

        //存放用来更新的，不断通过松弛操作来更新值，
        //更新完之后就将最小的值放到selectPaths里面去代表它被拽起来了
        //再将它从 paths中 remove
        Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
        Map<V, PathInfo<V, E>> selectPaths = new HashMap<>();
        //初始化paths
        paths.put(beginVertex, new PathInfo<>(weightManager.zero()));
//        for (Edge<V, E> edge : beginVertex.outEdges) {
//            PathInfo<V, E> path = new PathInfo<>();
//            path.weight = edge.weight;
//            path.edgeInfos.add(edge.info());
//            paths.put(edge.to, path);
//        }

        while (!paths.isEmpty()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath2(paths);
            //minEntry离开桌面
            Vertex<V, E> minVertex = minEntry.getKey();
            PathInfo<V, E> minPath = minEntry.getValue();
            selectPaths.put(minVertex.value, minPath);
            paths.remove(minVertex);
            //对 minVertex 的 outEdegs 进行松弛操作
            for (Edge<V, E> edge : minVertex.outEdges) {
                //如果edge.to已经离开桌面，或者edge.to是起点，就没有必要进行松弛操作
                if (selectPaths.containsKey(edge.to.value)) continue;
                    relaxForDijkstra(edge, minPath,paths);
            }
        }
        selectPaths.remove(begin);
        return selectPaths;
    }
    /**
     * 第二种 Dijkstra 的 getMinPath 方法，从path里面挑一个最小的路径出来
     *
     * @param paths
     * @return
     */
    private Map.Entry<Vertex<V, E>, PathInfo<V, E>> getMinPath2(Map<Vertex<V, E>, PathInfo<V, E>> paths) {
        Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> it = paths.entrySet().iterator();
        Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = it.next();
        while (it.hasNext()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> entry = it.next();
            if (weightManager.compare(entry.getValue().weight, minEntry.getValue().weight) < 0) {
                minEntry = entry;
            }
        }
        return minEntry;
    }
    /**
     * Dijkstra的松弛操作
     * 松弛操作用于找到其他点和原点更短的路径
     *
     * @param edge 需要松弛的边
     * @param fromPath edge的from的最短路径信息
     * @param paths 存放着其他点（就是还没有离开桌面的点）的最短路径信息
     */
    private void relaxForDijkstra(Edge<V, E> edge ,PathInfo<V, E> fromPath ,Map<Vertex<V, E>, PathInfo<V, E>> paths) {
        //新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        //以前的最短路径：beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPath = paths.get(edge.to);

        if (oldPath != null || weightManager.compare(newWeight, oldPath.weight) >= 0) return;
        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }
        oldPath.weight = newWeight;
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        oldPath.edgeInfos.add(edge.info());
    }

    /**
     * 最短路径 Bellman-ford算法
     * @param begin
     * @return
     */
    public Map<V,PathInfo<V,E>> bellmanFord(V begin){
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;

        Map<V, PathInfo<V, E>> selectPaths = new HashMap<>();
        //为了防止Map永远为空的情况，定义一个从begin到begin的最短路径放到map
        //不要添加路径信息，直接将begin作为key，begin到begin的权值是零
        PathInfo<V, E> beginPath = new PathInfo<>(weightManager.zero());
        selectPaths.put(begin, beginPath);

        //进行 n-1松弛，n为顶点数量
        int count = vertices.size() - 1;
        for (int i = 0; i < count; i++) {
            for (Edge<V, E> edge : edges) {
                PathInfo<V, E> fromPath = selectPaths.get(edge.from.value);
                if (fromPath == null) continue;
                relaxForBellmanFord(edge, fromPath, selectPaths);
            }
        }

        //这个for循环用来检测是否有负权环，
        // 因为在进行了n-1次松弛之后，理论上已经将最短路径找出来
        //如果再来一次n-1此松弛又找到了新的最短路径则说明有负权环
        for (int i = 0; i < count; i++) {
            for (Edge<V, E> edge : edges) {
                PathInfo<V, E> fromPath = selectPaths.get(edge.from.value);
                if (fromPath == null) continue;
                //在这个地方还能松弛成功 返回true，那么就有负权环，返回空
                if (relaxForBellmanFord(edge, fromPath, selectPaths)) return null;
            }
        }
        selectPaths.remove(begin);
        return selectPaths;
    }
    /**
     * Bellman-ford算法的松弛操作
     * 返回boolean值，表示松弛成功还是失败
     *
     * @param edge
     * @param fromPath
     * @param paths
     * @return
     */
    private boolean relaxForBellmanFord(Edge<V, E> edge ,PathInfo<V, E> fromPath ,Map<V, PathInfo<V, E>> paths) {
        //新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        //以前的最短路径：beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPath = paths.get(edge.to.value);

        if (oldPath != null || weightManager.compare(newWeight, oldPath.weight) >= 0) return false;
        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to.value, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }
        oldPath.weight = newWeight;
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        oldPath.edgeInfos.add(edge.info());

        return true;
    }

    /**
     * 多源最短路径算法
     *
     * @return
     */
    @Override
    public Map<V, Map<V, PathInfo<V, E>>> shortestPath() {
        Map<V, Map<V, PathInfo<V,  E>>> paths = new HashMap<>();
        //初始化
        for (Edge<V, E> edge : edges) {
            Map<V, PathInfo<V, E>> map = paths.get(edge.from.value);
            if (map == null) {
                map = new HashMap<>();
                paths.put(edge.from.value, map);
            }

            PathInfo<V,E>  pathInfo = new PathInfo<>(edge.weight);
            pathInfo.edgeInfos.add(edge.info());
            map.put(edge.to.value, pathInfo);
        }

        vertices.forEach((V v2, Vertex<V,E>vertex2) -> {
            vertices.forEach((V v1, Vertex<V,E>vertex1) -> {
                vertices.forEach((V v3, Vertex<V,E>vertex3) -> {
                    if (v1.equals(v2) || v2.equals(v3) || v1.equals(v2)) return;

                    //v1 -> v2 的最短路径
                    PathInfo<V, E> path12 = getPathInfo(v1, v2, paths);
                    if (path12 == null) return;

                    //v2 -> v3 的最短路径
                    PathInfo<V, E> path23 = getPathInfo(v2, v3, paths);
                    if (path23 == null) return;

                    //v1 -> v3 的最短路径
                    PathInfo<V, E> path13 = getPathInfo(v1, v3, paths);

                    E newWeight = weightManager.add(path12.weight, path23.weight);
                    if (path13 != null && weightManager.compare(newWeight, path23.weight) >= 0) return;

                    if (path13 == null){
                        path13 = new PathInfo<V,E>();
                        paths.get(v1).put(v3, path13);
                    }else {
                        path13.edgeInfos.clear();
                    }

                    path13.weight = newWeight;
                    path13.edgeInfos.addAll(path12.edgeInfos);
                    path13.edgeInfos.addAll(path23.edgeInfos);
                });
            });
        });

        return paths;
    }
    private PathInfo<V, E> getPathInfo(V from, V to, Map<V, Map<V, PathInfo<V, E>>> paths) {
        Map<V, PathInfo<V, E>> map = paths.get(from);
        return map == null ? null : map.get(to);
    }
}
